package cn.initcap.algorithm.graph;

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.TreeSet;

/**
 * 稀疏图 - 邻接表
 *
 * @author initcap
 * @date Created in 1/20/19 12:51 PM.
 */
public class SparseGraph<W extends Number & Comparable> implements Graph<Integer, W> {

    /**
     * 节点数
     */
    private int node;
    /**
     * 边数
     */
    private int margin;
    /**
     * 是否为有向图
     */
    private boolean directed;
    /**
     * 记录入度和出度
     */
    private int[] indegree, outdegree;
    /**
     * 图的具体数据
     */
    private List<TreeSet<Integer>> g;

    /**
     * 根据文件构建图
     *
     * @param filename 文件名称
     * @param directed 是否为有向图
     */
    public SparseGraph(String filename, boolean directed) {
        this.directed = directed;
        File file = new File(filename);

        try (Scanner scanner = new Scanner(file)) {

            node = scanner.nextInt();
            if (node < 0) {
                throw new IllegalArgumentException("node must be non-negative");
            }

            indegree = new int[node];
            outdegree = new int[node];
            int e = scanner.nextInt();
            if (e < 0) {
                throw new IllegalArgumentException("margin must be non-negative");
            }

            for (int i = 0; i < e; i++) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();

                if (a == b) {
                    throw new IllegalArgumentException("Self Loop is Detected!");
                }
                if (directed) {
                    indegree[b]++;
                    outdegree[a]++;
                }
                addEdge(new Edge(a, b, 0.0));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 返回节点个数
     *
     * @return 节点数
     */
    @Override
    public int nodeSize() {
        return node;
    }

    /**
     * 返回边的个数
     *
     * @return 边数
     */
    @Override
    public int marginSize() {
        return margin;
    }

    /**
     * 向图中添加一个边(先不考虑平行边的问题)
     *
     * @param e 边信息
     */
    @Override
    public void addEdge(Edge e) {
        if (g == null) {
            g = new ArrayList<>(node);
            for (int i = 0; i < node; i++) {
                g.add(new TreeSet<>());
            }
        }

        validateVertex(e.v(), this.node);
        validateVertex(e.w(), this.node);

        g.get(e.v()).add(e.w());
        if (e.v() != e.w() && !directed) {
            g.get(e.w()).add(e.v());
        }

        margin++;
    }

    /**
     * 验证图中是否有从v到w的边
     *
     * @param v 开始节点
     * @param w 目标节点
     * @return
     */
    @Override
    public boolean hasEdge(int v, int w) {
        validateVertex(v, this.node);
        validateVertex(w, this.node);

        for (int x : g.get(v)) {
            if (x == w) {
                return true;
            }
        }
        return false;
    }

    /**
     * 显示图的信息
     */
    @Override
    public void show() {
        for (int i = 0; i < node; i++) {
            System.out.print("vertex " + i + ":\t");
            for (int x : g.get(i)) {
                System.out.print(x + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 返回图中一个顶点的所有邻边
     * 由于java使用引用机制，返回一个TreeSet不会带来额外开销,
     *
     * @param v
     * @return
     */
    @Override
    public Iterable<Integer> adj(int v) {
        validateVertex(v, this.node);
        return g.get(v);
    }

    @Override
    public int indegree(int v) {
        if (!isDirected()) {
            throw new IllegalArgumentException("undirected graph no indegree!");
        }
        return this.indegree[v];
    }

    @Override
    public int outdegree(int v) {
        if (!isDirected()) {
            throw new IllegalArgumentException("undirected graph no outdegree!");
        }
        return this.outdegree[v];
    }

    @Override
    public boolean isDirected() {
        return this.directed;
    }

}
